package algocasts;

public class P86_sortedThreeColorsCount {
    // Time: O(n)  Space: O(n)
    public void sortThreeColors_Count(int[] nums) {
        if (nums == null || nums.length == 0) return;
        int c0 = 0, c1 = 0, c2 = 0;
        for (int num : nums) {
            if (num == 0) c0++;
            else if (num == 1) c1++;
            else c2++;
        }
        int k = 0;
        for (int i = 0; i < c0; ++i) nums[k++] = 0;
        for (int i = 0; i < c1; ++i) nums[k++] = 1;
        for (int i = 0; i < c2; ++i) nums[k++] = 2;
    }

    // Time: O(n)  Space: O(1)
    public void sortThreeColors_Swap(int[] nums) {
        if (nums == null || nums.length == 0) return;
        int left = 0, mid = 0, right = nums.length - 1;
        while (mid <= right) {
            if (nums[mid] == 0) swap(nums, mid++, left++);
            else if (nums[mid] == 1) mid++;
            else swap(nums, mid, right--);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
